package cn.edu.xjtu.work.getIntersectionNode;

import cn.edu.xjtu.Util.ListNode.ListNode;

import java.util.HashSet;
import java.util.Set;


/**
 * 160. 相交链表
 * 
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 */
public class Solution {
  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Set<ListNode> set = new HashSet<>();
    ListNode temp = headA;
    while (temp != null) {
      set.add(temp);
      temp = temp.next;
    }
    temp = headB;
    while (temp != null) {
      if (set.contains(temp)) {
        return temp;
      }
      temp = temp.next;
    }
    return null;
  }
}
